package cn.good.yan.sf.t1;

/**
 * 1. 线性查找法 、二分查找
 *
 * @author shengren.yan
 * @create 2024-04-11
 */
public class Demo1 {

    // 二分查找
    private static final int[] ARR = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};

    /**
     * 查 3
     *            i     j      m
     * 第一次循环 ：0     9      4   满足 3 < 5
     * 第二次循环 ：0     3      1   满足 3 > 2
     * 第三次循环 ：2     3      2   都不满足 - 结束循环 返回下标 2
     */

    /**
     * 二分查找法：
     *
     * @param arr    数组，（升序/降序）
     * @param target 要查询到值
     * @return int 查询到会返回（该值的下标），没有查询到返回（-1）
     */
    public static int binarySearchA(int[] arr, int target) {
        int i = 0;
        int j = arr.length - 1;
        while (i <= j) {
//            int m = (j + i) / 2;   // 中间值 （向下取整）
            int m = (j + i) >>> 1;   // 优化部分 中间值 （向下取整） , 如果int值是最大的值，会出现负数
            if (target < arr[m]) {
                // 左边位置
                j = m - 1;
            } else if (arr[m] < target) {
                // 右边位置
                i = m + 1;
            } else {
                // 当前位置
                return m;
            }
        }
        return -1;
    }

    /**
     * 查 3
     *            i     j      m
     * 第一次循环 ：0     10     5   满足 3 < 6
     * 第二次循环 ：0     5      2   都不满足 - 结束循环 返回下标 2
     * binarySearchB 方法 比 binarySearchA  少1次循环
     */

    /**
     * 二分查找法：
     *
     * @param arr    数组，（升序/降序）
     * @param target 要查询到值
     * @return int 查询到会返回（该值的下标），没有查询到返回（-1）
     */
    public static int binarySearchB(int[] arr, int target) {
        int i = 0;
        int j = arr.length;
        while (i < j) {
            int m = (j + i) / 2;       // 中间值 （向下取整）
            if (target < arr[m]) {
                // 左边位置
                j = m;
            } else if (arr[m] < target) {
                // 右边位置
                i = m + 1;
            } else {
                // 当前位置
                return m;
            }
        }
        return -1;
    }

    /**
     * 二分查找法： - 优化版本，先找到位置，再if比较
     *
     * @param arr    数组，（升序/降序）
     * @param target 要查询到值
     * @return int 查询到会返回（该值的下标），没有查询到返回（-1）
     */
    private static int binarySearchC(int[] arr, int target) {
        System.out.println("当前节点" + target);   //  7
//      int[] arr = {1, 2, 3, 4,5,6,7,8,null};    /
        int i = 0;            // 4
        int j = arr.length;   // 8
        while ((j - i) > 1) {
            int m = (i + j) / 2;  // 中间值   3
            if (target < arr[m]) {
                j = m;
            } else {
                i = m;
            }
        }
        if (arr[i] == target) {
            return i;
        } else {
            return -1;
        }
    }


    /**
     * 线性查找法：
     *
     * @param arr    数组，（升序/降序）
     * @param target 要查询到值
     * @return int 查询到会返回（该值的下标），没有查询到返回（-1）
     */
    public static int linearySearch(int[] arr, int target) {
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == target) {
                return i;
            }
        }
        return -1;
    }


    public static void main(String[] args) {
        // 二分查找: 方式1：
        int[] arr = ARR;
        int i = binarySearchA(arr, 6);
        System.out.println("得到下标值" + i);
        // 二分查找: 方式2：优势
        int[] arr2 = ARR;
        int i2 = binarySearchB(arr2, 6);
        System.out.println("得到下标值" + i2);

        // 线性查找法:
        int[] arr3 = ARR;
        int i3 = linearySearch(arr3, 6);
        System.out.println("得到下标值" + i);
    }

}
